SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Anytime algorithm</title>

</head>

Anytime algorithm

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, an anytime algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> that can return a valid solution to a <a href="Computational_problem" title="Computational problem">problem</a> even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running.

Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer.

<div class="mw-heading mw-heading2"><h2 id="Names">Names</h2></div>

An anytime algorithm may be also called an "interruptible algorithm". They are different from contract algorithms, which must declare a time in advance; in an anytime algorithm, a process can just announce that it is terminating.<a href="#cite_note-Hendler-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Goals">Goals</h2></div>

The goal of anytime algorithms are to give <a href="Hybrid_intelligent_system" title="Hybrid intelligent system">intelligent systems</a> the ability to make results of better quality in return for turn-around time.<a href="#cite_note-Zilberstein-2">[2]</a> They are also supposed to be flexible in time and resources.<a href="#cite_note-Grass-3">[3]</a> They are important because <a href="Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a> or AI algorithms can take a long time to complete results. This algorithm is designed to complete in a shorter amount of time.<a href="#cite_note-Grass-3">[3]</a> Also, these are intended to have a better understanding that the system is dependent and restricted to its agents and how they work cooperatively.<a href="#cite_note-Grass-3">[3]</a> An example is the <a href="Newton%E2%80%93Raphson" class="mw-redirect" title="Newton–Raphson">Newton–Raphson</a> iteration applied to finding the square root of a number.<a href="#cite_note-FOLDOC-4">[4]</a> Another example that uses anytime algorithms is trajectory problems when you're aiming for a target; the object is moving through space while waiting for the algorithm to finish and even an approximate answer can significantly improve its accuracy if given early.<a href="#cite_note-Grass-3">[3]</a>

What makes anytime algorithms unique is their ability to return many possible outcomes for any given input.<a href="#cite_note-Zilberstein-2">[2]</a> An anytime algorithm uses many well defined quality measures to monitor progress in <a href="Problem_solving" title="Problem solving">problem solving</a> and <a href="Distributed_computing" title="Distributed computing">distributed computing</a> resources.<a href="#cite_note-Zilberstein-2">[2]</a> It keeps searching for the best possible answer with the amount of time that it is given.<a href="#cite_note-umich-5">[5]</a> It may not run until completion and may improve the answer if it is allowed to run longer.<a href="#cite_note-elook-6">[6]</a>

This is often used for large decision set problems.<a href="#cite_note-Horsch-7">[7]</a> This would generally not provide useful information unless it is allowed to finish.<a href="#cite_note-Bender-8">[8]</a> While this may sound similar to <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>, the difference is that it is fine-tuned through random adjustments, rather than sequential.

Anytime algorithms are designed so that it can be told to stop at any time and would return the best result it has found so far.<a href="#cite_note-Grass-3">[3]</a> This is why it is called an interruptible algorithm. Certain anytime algorithms also maintain the last result, so that if they are given more time, they can continue from where they left off to obtain an even better result.<a href="#cite_note-Grass-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Decision_trees">Decision trees</h2></div>

When the decider has to act, there must be some ambiguity. Also, there must be some idea about how to solve this ambiguity. This idea must be translatable to a state to action diagram.<a href="#cite_note-Horsch-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Performance_profile">Performance profile</h2></div>

The performance profile estimates the quality of the results based on the input and the amount of time that is allotted to the algorithm.<a href="#cite_note-Grass-3">[3]</a> The better the estimate, the sooner the result would be found.<a href="#cite_note-Grass-3">[3]</a> Some systems have a larger database that gives the probability that the output is the expected output.<a href="#cite_note-Grass-3">[3]</a> It is important to note that one algorithm can have several performance profiles.<a href="#cite_note-Teije-9">[9]</a> Most of the time performance profiles are constructed using <a href="Mathematical_statistics" title="Mathematical statistics">mathematical statistics</a> using representative cases. For example, in the <a href="Travelling_salesman_problem" title="Travelling salesman problem">traveling salesman</a> problem, the performance profile was generated using a user-defined special program to generate the necessary statistics.<a href="#cite_note-Hendler-1">[1]</a> In this example, the performance profile is the mapping of time to the expected results.<a href="#cite_note-Hendler-1">[1]</a> This quality can be measured in several ways:

<ul><li>certainty: where probability of correctness determines quality<a href="#cite_note-Hendler-1">[1]</a></li>

<li>accuracy: where error bound determines quality<a href="#cite_note-Hendler-1">[1]</a></li>

<li>specificity: where the amount of particulars determine quality<a href="#cite_note-Hendler-1">[1]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Algorithm_prerequisites">Algorithm prerequisites</h2></div>

Initial behavior: While some algorithms start with immediate guesses, others take a more calculated approach and have a start up period before making any guesses.<a href="#cite_note-Teije-9">[9]</a>

<ul><li>Growth direction: How the quality of the program's "output" or result, varies as a function of the amount of time ("run time")<a href="#cite_note-Teije-9">[9]</a></li>

<li>Growth rate: Amount of increase with each step. Does it change constantly, such as in a <a href="Bubble_sort" title="Bubble sort">bubble sort</a> or does it change unpredictably?</li>

<li>End condition: The amount of runtime needed<a href="#cite_note-Teije-9">[9]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHendler2014" class="citation book cs1">Hendler, James A., ed. (2014) [1992]. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=tgujBQAAQBAJ&pg=PR5">Artificial Intelligence Planning Systems: Proceedings of the First Conference (AIPS 92)</a>. Elsevier. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-08-049944-4</bdi>.</cite>

</li>

<li id="cite_note-Zilberstein-2">^ <a href="#cite_ref-Zilberstein_2-0">a</a> <a href="#cite_ref-Zilberstein_2-1">b</a> <a href="#cite_ref-Zilberstein_2-2">c</a> <a href="#CITEREFZilberstein1996">Zilberstein 1996</a>

</li>

<li id="cite_note-Grass-3">^ <a href="#cite_ref-Grass_3-0">a</a> <a href="#cite_ref-Grass_3-1">b</a> <a href="#cite_ref-Grass_3-2">c</a> <a href="#cite_ref-Grass_3-3">d</a> <a href="#cite_ref-Grass_3-4">e</a> <a href="#cite_ref-Grass_3-5">f</a> <a href="#cite_ref-Grass_3-6">g</a> <a href="#cite_ref-Grass_3-7">h</a> <a href="#cite_ref-Grass_3-8">i</a> <cite id="CITEREFGrass1996" class="citation journal cs1">Grass, J. (1996). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F332148.332154">"Reasoning about computational resource allocation"</a>. XRDS: Crossroads, the ACM Magazine for Students. 3 (1): 16–20. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F332148.332154">10.1145/332148.332154</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:45448244">45448244</a>.</cite>

</li>

<li id="cite_note-FOLDOC-4"><a href="#cite_ref-FOLDOC_4-0">^</a> <a rel="nofollow" class="external text" href="http://foldoc.org/anytime+algorithm">anytime algorithm from Free Online Dictionary of Computing (FOLDOC)</a>

</li>

<li id="cite_note-umich-5"><a href="#cite_ref-umich_5-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131213011435/http://ai.eecs.umich.edu/cogarch2/cap/anytime.plan">"Anytime algorithms"</a>. Cognitive architectures. University of Michigan Artificial Intelligence Laboratory. Archived from <a rel="nofollow" class="external text" href="http://ai.eecs.umich.edu/cogarch2/index.html">the original</a> on 13 December 2013.</cite>

</li>

<li id="cite_note-elook-6"><a href="#cite_ref-elook_6-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131212094200/http://www.elook.org/computing/anytime-algorithm.htm">"Anytime algorithm - Computing Reference"</a>. eLook.org. Archived from <a rel="nofollow" class="external text" href="http://www.elook.org/computing/anytime-algorithm.htm">the original</a> on 12 December 2013.</cite>

</li>

<li id="cite_note-Horsch-7">^ <a href="#cite_ref-Horsch_7-0">a</a> <a href="#cite_ref-Horsch_7-1">b</a> <a href="#CITEREFHorschPoole1998">Horsch & Poole 1998</a>

</li>

<li id="cite_note-Bender-8"><a href="#cite_ref-Bender_8-0">^</a> <cite id="CITEREFBender1996" class="citation book cs1">Bender, Edward A. (1996). Mathematical Methods In Artificial Intelligence. Wiley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8186-7200-2</bdi>.</cite>

</li>

<li id="cite_note-Teije-9">^ <a href="#cite_ref-Teije_9-0">a</a> <a href="#cite_ref-Teije_9-1">b</a> <a href="#cite_ref-Teije_9-2">c</a> <a href="#cite_ref-Teije_9-3">d</a> <cite id="CITEREFTeijevan_Harmelen2000" class="citation conference cs1">Teije, A.T.; van Harmelen, F. (2000). <a rel="nofollow" class="external text" href="https://core.ac.uk/download/pdf/43408018.pdf">"Describing problem solving methods using anytime performance profiles"</a> (PDF). Proceedings of the 14th European Conference on Artificial Intelligence. pp. 181–5.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFBoddyDean1989" class="citation conference cs1">Boddy, M.; Dean, T. (1989). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/1623891.1623912">"Solving time-dependent planning problems"</a>. Proceedings of the 11th international joint conference on Artificial intelligence. Vol. 2. pp. 979–984. Brown University CS-89-03.</cite></li>

<li><cite id="CITEREFGrassZilberstein1996" class="citation journal cs1">Grass, J.; Zilberstein, S. (1996). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.1145/242587.242592">"Anytime Algorithm Development Tools"</a>. ACM SIGART Bulletin. 7 (2 Special Issue on Anytime Algorithms and Deliberation Scheduling): 20–27. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F242587.242592">10.1145/242587.242592</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7670055">7670055</a>.</cite></li>

<li><cite id="CITEREFHorschPoole1998" class="citation conference cs1">Horsch, M.C.; Poole, D. (1998). <a rel="nofollow" class="external text" href="http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf">"An anytime algorithm for decision making under uncertainty"</a> (PDF). Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence. pp. 246–255. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1301.7384">1301.7384</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-555-8</bdi>.</cite></li>

<li><cite id="CITEREFHorvitz1986" class="citation techreport cs1">Horvitz, E.J. (March 1986). Reasoning about inference tradeoffs in a world of bounded resources (Technical report). Medical Computer Science Group, Section on Medical Informatics, Stanford University. KSL-86-55.</cite></li>

<li><cite id="CITEREFWallaceFreuder1995" class="citation journal cs1">Wallace, R.; Freuder, E. (1995). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F242587.242589">"Anytime Algorithms for Constraint Satisfaction and SAT Problems"</a>. ACM SIGART Bulletin. 7 (2): 7–10. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F242587.242589">10.1145/242587.242589</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8250394">8250394</a>.</cite></li>

<li><cite id="CITEREFZilberstein1993" class="citation thesis cs1">Zilberstein, S. (1993). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/193131">Operational Rationality through Compilation of Anytime Algorithms</a> (PhD). Computer Science Division, University of California at Berkeley. UMX GAX94-08166.</cite></li>

<li><cite id="CITEREFZilberstein1996" class="citation journal cs1">Zilberstein, Shlomo (1996). <a rel="nofollow" class="external text" href="http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf">"Using Anytime Algorithms in Intelligent Systems"</a> (PDF). AI Magazine. 17 (3): 73–83.</cite></li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-06" href="https://en.wikipedia.org/wiki/?title=Anytime_algorithm&oldid=1294189594">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>